import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * @Author: wangliuyang
 * @Date: 2021/9/6 19:16
 * @Description:
 */
public class Solution_47 {
    class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            List<List<Integer>> list = new ArrayList<>();
            permuted(nums, 0, list);
            return list;
        }

        public void permuted(int[] nums, int index, List<List<Integer>> list) {
            if (index == nums.length) {
                ArrayList<Integer> arrayList = new ArrayList<>();
                for (int num : nums) {
                    arrayList.add(num);
                }
                list.add(arrayList);
                return;
            }
            HashSet<Integer> set = new HashSet<>();
            for (int i = index; i < nums.length; i++) {
                if (!set.contains(nums[i])) {
                    set.add(nums[i]);
                    swap(nums, index, i);
                    permuted(nums, index + 1, list);
                    swap(nums, index, i);
                }
            }
        }

        private void swap(int[] nums, int index, int i) {
            if (index == i) {
                return;
            }
            nums[index] = nums[i] ^ nums[index];
            nums[i] = nums[i] ^ nums[index];
            nums[index] = nums[i] ^ nums[index];
        }
    }
}
